class Solution {
public:
    vector<vector<string>> solveNQueens(int n)
    {
        string s(n, '.');
        vector<vector<string>> ans;
        vector<string> path(n, s);
        function<void(int)> dfs = [&](int i) {
            if (i == n)
            {
                ans.push_back(path);
                return;
            }
            for (int j = 0; j < n; j++)
            {
                bool flag = false;
                for (int k = 0; k <= i; k++)
                {
                    if (path[k][j] == 'Q')
                    {
                        flag = true;
                        break;
                    }
                }
                if (!flag)
                {
                    for (int a = i, b = j; a >= 0 && b >= 0; a--, b--)
                    {
                        if (path[a][b] == 'Q')
                        {
                            flag = true;
                            break;
                        }
                    }
                }
                if (!flag)
                {
                    for (int a = i, b = j; a >= 0 && b < n; a--, b++)
                    {
                        if (path[a][b] == 'Q')
                        {
                            flag = true;
                            break;
                        }
                    }
                }
                if (flag) continue;
                path[i][j] = 'Q';
                dfs(i + 1);
                path[i][j] = '.';
            }
            };
        dfs(0);
        return ans;
    }
};